package com.github.hgkmail.hello.leetcode101.sort;

import com.github.hgkmail.hello.leetcode101.base.CommonUtil;

public class LC215KthLargestElementInAnArray {
    //左闭右开
    //先r--，再l++
    public int partition(int[] nums, int l, int r) {
        int key=nums[l];
        int i=l;
        int j=r-1;
        while (i<j) {
            while (i<j && nums[j]>=key) j--;
            while (i<j && nums[i]<=key) i++;
            if (i<j) {
                CommonUtil.swap(nums, i, j);
            }
        }
        CommonUtil.swap(nums, l, i);
        return i;
    }
    //找第k大，其实就是快排
    public int findKthLargest(int[] nums, int k) {
        if (nums.length<k) {
            return 0;
        }
        int l=0;
        int r=nums.length;
        int rank=k;
        while (l<r) {
            int pivot = partition(nums, l, r);
            if (r-pivot==rank) {
                return nums[pivot];
            } else if (r-pivot>rank) { //k在右边
                l=pivot+1;
            } else if (r-pivot<rank) { //k在左边，这时要更新排名
                rank-=r-pivot;
                r=pivot;
            }
        }
        return 0;
    }
    public static void main(String[] args) {
        System.out.println(new LC215KthLargestElementInAnArray().findKthLargest(new int[]{2,1}, 2));
    }
}
